package reviewAlgorithms.dynamicProgramming;

import java.util.Arrays;

public class Largest1BorderedSquare {
    public static void main(String[] args) {
        int[][] grid = {{0,1},{1,1}};
        System.out.println(largest1BorderedSquare(grid));
    }

    public static int largest1BorderedSquare(int[][] grid) {
        if (grid == null || grid.length < 1){
            return 0;
        }
        int[][][] dp = new int[grid.length][grid[0].length][2];
        int max = 0;
        if (grid[0][0] == 1){
            dp[0][0][0] = 1;//上
            dp[0][0][1] = 1;//左
            max = 1;
        }
        for (int i = 1; i < grid.length; i++) {
            dp[i][0][0] = 1;
            if (grid[i][0] == 1){
                dp[i][0][1] = dp[i - 1][0][1] + 1;
                max = 1;
            }else {
                dp[i][0][1] = 0;
            }
        }

        for (int i = 1; i < grid[0].length; i++) {
            dp[0][i][1] = 1;
            if (grid[0][i] == 1){
                dp[0][i][0] = dp[0][i - 1][0] + 1;
                max = 1;
            }else {
                dp[0][i][0] = 0;
            }
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                if (grid[i][j] == 1){
                    dp[i][j][0] = dp[i][j - 1][0] + 1;
                    dp[i][j][1] = dp[i - 1][j][1] + 1;
                    max = Math.max(max,getCurMax(dp,i,j));
                }else {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                }
            }

        }
        return max;
    }

    private static int getCurMax(int[][][] dp, int i, int j) {
        int up = dp[i][j][0];
        int left = dp[i][j][1];
        int min = Math.min(up,left);
        int res = 0;
        for (int k = 0; k < min; k++) {
            if (dp[i - k][j][0] > k && dp[i][j - k][1] > k){
                res = Math.max(res,(k + 1) * (k + 1));
            }
        }
        return res;
    }
}
